This invention relates to a route searching system of a navigation apparatus used for finding the shortest route from a given point to a destination.
Navigation apparatus are known which are used to guide a driver who is not particularly familiar with a region to his destination in that region by selecting a suitable course leading thereto. Apparatus of this kind are now being developed eagerly.
In a conventional navigation apparatus, a course along which a driver will be led to his destination is set on the basis of a starting point and a destination point which are input before the driver starts traveling. The driver navigates along the course thereby set. There are various systems of designating a desired course during navigation, such as one in which a map is displayed on a CRT screen and an image of the course is superposed on the map. Another system displays information about an intersection where the driver needs to turn the vehicle in accordance with a predetermined course which information includes numerals or a graph indicating the distance remaining until the intersection is reached and a picture showing certain features of the intersection. A further system makes use of speech output as an auxiliary means.
Ordinarily, in a road system, a plurality of courses which connect a starting point and a destination point could in theory be selected. For this reason, various methods of searching for a shortest-time or shortest-distance course (shortest course) between a desired starting point and destination point have been proposed for use in such navigation apparatus. One example of such a method has been reported in which an intersection, such as that shown in FIG. 9, is represented by eight nodes and sixteen directional links to express left and right turns, straight-ahead travel and U-turns, and in which each of the roads connecting the intersections are represented by a pair of directional links. In another example (such as the one disclosed in Japanese Patent Laid-Open No. 62-91811), the shortest course is found by comparing data on courses along which travel is prohibited, and if travel is prohibited, the course is removed, thereby finding the shortest courses which includes no impassable section.
The former method entails a problem, however, in that all items of information on left/right turns at intersections are represented by directional links, so the total quantity of data and, hence, the memory capacity is high. In addition, a process of finding a shortest-time course from data having a conventional data structure by detecting left and right turns and weighing data items with the detected left and right turns requires a complicated process of computation for determining left and right turns, resulting in an increased searching time. Specifically, where a crossroad is represented by eight nodes and sixteen directional links, weighted items of data on distance or time must be prepared with respect to each of the sixteen directional links.